class Solution
{
public:
    int mySqrt(int x)
    {
        if (!x)
            return 0;
        int l = 1, r = x, mid = ((long long)l + r) / 2;

        while (l + 1 != r)
        {
            if (mid <= x / mid and (mid + 1) > x / (mid + 1))
                return mid;

            if (mid < x / mid)
                l = mid;

            else
                r = mid;

            mid = (l + r) / 2;
        }
        return l;
    }
};